package leetcode.string;

/*
 5. 最长回文子串

 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

 示例 1：
 输入: "babad"
 输出: "bab"
 注意: "aba" 也是一个有效答案。

 示例 2：
 输入: "cbbd"
 输出: "bb"
*/

public class LongestPalindrome5 {

    public static void main(String[] args) {

//        String s = "babad";
        String s = "cbbd";

        System.out.println(s);
        System.out.println(test(s));
    }

    public static String test(String s) {
        if(null == s)
            return null;
        if(2 > s.length())
            return s;

//        return settle1(s);
        return settle2(s);
    }

    // 暴力破解
    private static String settle1(String s) {
        int start = 0, len = 1;
        char[] charArray = s.toCharArray();

        int t;
        for(int i = 0; i < s.length() - 1; i++) {
            for (int j = i+1; j < s.length(); j++) {
                t = j - i + 1;
                if(t > len && findByViolence(charArray, i, j)) {
                    len = t;
                    start = i;
                }
            }
        }

        return s.substring(start, start + len);
    }

    private static boolean findByViolence(char[] array, int left, int right) {
        while(left < right) {
            if(array[left] != array[right])
                return false;

            left++;
            right--;
        }

        return true;
    }

    // 动态规划
    private static String settle2(String s) {
        int start = 0, len = 1;
        char[] charArray = s.toCharArray();

        boolean[][] t = new boolean[s.length()][s.length()];
        for(int i = 0; i < s.length(); i++) {
            t[i][i] = true;
        }

        for(int j = 1; j < s.length(); j++) {
            for (int i = 0; i < j; i++) {
                if(charArray[i] != charArray[j]) {
                    t[i][j] = false;
                } else {
                    if(j - i < 3)
                        t[i][j] = true;
                    else
                        t[i][j] = t[i + 1][j - 1];
                }

                if(t[i][j] && j - i + 1 > len) {
                    len = j - i + 1;
                    start = i;
                }
            }
        }

        return s.substring(start, start + len);
    }
}
